package com.leetcode.bfs_dfs;

import com.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Leetcode102 {

    /*
    solution 1:广度优先搜索（BFS）
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }

        //以下面的测试用例来说明：root ：3，先加入到queue中
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            //第一次只有root，因此levelSize是1
            int levelSize = queue.size();
            List<Integer> levelList = new ArrayList<>();
            for(int i=0; i<levelSize; i++){
                //按顺序取出queue中的元素
                TreeNode curr = queue.poll();
                //将当前节点的值存储到levelList中
                levelList.add(curr.val);
                //遍历当前节点的左右子树，并且按顺序加入到queue中
                //第一次循环结束之后，就将root的左右子树加入到queue中,levelSize就变成2
                if(curr.left != null){
                    queue.offer(curr.left);
                }

                if(curr.right != null){
                    queue.offer((curr.right));
                }
            }

            ans.add(levelList);
        }

        return ans;
    }
*/


    /**
     * class Solution {
     * private:
     *     vector<vector<int>> res;
     *     void dfs(TreeNode* node, int level) {
     *     	//当前层还未生成动态数组时，插入一个空数组
     *         if(res.size() == level) {
     *             vector<int> empty;
     *             res.push_back(empty);
     *         }
     *         res[level].push_back(node->val);
     *         if(node->left) dfs(node->left, level+1);
     *         if(node->right) dfs(node->right, level+1);
     *     }
     * public:
     *     vector<vector<int>> levelOrder(TreeNode* root) {
     *         if(root == nullptr) return res;
     *         dfs(root, 0);
     *         return res;
     *     }
     * };
     */

    /*
    solution 2:  深度优先搜索（DFS）
    遍历的时候还是使用递归的方法，按深度遍历的顺序遍历
    遍历的顺序跟加入数组的顺序不一样，但是这里做了个小技巧
    ans.get(level).add(curr.val);ans可以理解是二维数组，加入新元素的时候，是按level来添加的
    这样子就可以保证对应的元素被添加到对应的level数组中
     */

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //从 0 开始
        levelOrder(root,0);
        return ans;
    }

    private void levelOrder(TreeNode curr,int level){
        if(curr == null){
            return ;
        }
        // level 从 0 开始算起，当ans.size 跟 level相等，表示还没申请新的元素
        if(ans.size() == level){
            ans.add(new ArrayList<>());
        }

        ans.get(level).add(curr.val);
        levelOrder(curr.left,level+1);
        levelOrder(curr.right,level+1);
    }
    /**
     *  测试程序
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * @param args
     */
    public static void main(String[] args){
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        root.left = left;
        root.right = right;
        TreeNode rleft = new TreeNode(15);
        TreeNode rright = new TreeNode(7);
        right.left = rleft;
        right.right = rright;

        Leetcode102 leetcode102 = new Leetcode102();
        System.out.println(leetcode102.levelOrder(root));
    }
}
